This invention relates to a landmark hierarchy method for routing signals in a communications network.
Switching nodes in computer and other communications networks execute routing functions to deliver data from source to destination. These routing functions involve (1) the storage of routing tables (memory overhead), (2) the exchange of routing updates with other nodes (link overhead), and (3) some set of algorithms to compute the routing table entries (CPU overhead). If the routing structure of the network is non-hierarchical, that is, every node maintains a routing entry for every other node in the network, then the overhead caused by the routing function is at best 0(N), N being the number of nodes in the network.
As networks grow to many thousands of nodes, the routing overhead can consume an unacceptable percentage of network resources. To overcome this problem, a hierarchical routing structure may be used which reduces the routing overhead. The penalty paid for reduced overhead is increased path length, the amount of which depends on the diameter and node degree of the network, but which is typically small. The telephone network is a well known example of a hierarchical routing structure.
Until now, only one hierarchical routing structure, the area (or cluster) hierarchy, has been developed. This routing structure has resulted in a very limited set of design alternatives for large network routing schemes. One of the problems with the area hierarchy is that it is very difficult to manage dynamically. That is, it is difficult to adjust the area hierarchy in response to topological changes in a distributed, dynamic fashion. In particular, problems arise in situations where a previously connected area is no longer connected, causing nodes to be unreachable by the routing algorithms even though there are physical paths to those nodes. This is referred to as an area partition, or simply, partition. The problem of managing partitions when they occur infrequently has been solved. This solution is adequate for stable networks but not in networks where the topologies may not be stable. A full solution to the problem of dynamic management of a area hierarchy is very difficult and has not yet been achieved in practice.
The area hierarchy approach is illustrated in FIG. 1 which shows a computer network of arbitrary physical topology, that is, the topology does not have an obvious physical structure to it such as a hierarchy, ring, etc. An area hierarchy has been overlaid on the network of FIG. 1. This hierarchy is created by logically grouping nodes into areas, grouping areas into super-areas, and so on.
To route a message in an area hierarchy, a node examines the address of the destination node (the telephone number is a well-known example of such an address), determines which area the node is in, and routes the message to that area. Nodes in that area then further route the message to a subarea, and so on until the message reaches its destination. This approach allows nodes outside an area to view the area as a single entity. The result is that only one entry is required in that node's routing table to route to several nodes in another area. For instance, in FIG. 1, node 2.1.1 views nodes 2.2.1, 2.2.2, and 2.2.3 as a single entity, namely, 2.2, which results in a savings of three to one in memory usage (for the table entries) and in link usage (for the updates required to maintain that entry).
As stated above, the penalty paid for this savings is increased path length. Using mathematical analysis it can be shown that, using the area hierarchy, routing overhead of no less than HN.sup.1/H, where H is the number of hierarchy levels, and N is the number of nodes, can be achieved. Simulation results on a 200-node network produce path lengths of 5% to 15% greater than the shortest path, and routing table sizes of forty or more nodes.